/*
 * 3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? 
 * Push, pop and min should all operate in O(1) time.
 */
public class StackWithMin1 {
	private LinkedListNode top;
	
	public StackWithMin1(){
		this.top = null;
	}
	
	public void push(int n){
		if(top == null) {
			LinkedListNode node = new LinkedListNode(n, n);
			top = node;
		}
		
		LinkedListNode node; 
		if(top.getMin() > n){
			node = new LinkedListNode(n, n);
		} else {
			node = new LinkedListNode(n, top.getMin());
		}
		
		node.next = top;
		top = node;
	}
	
	public int pop(){
		if (top == null)
			return Integer.MIN_VALUE;

		int n = top.data;
		top = top.next;

		return n;
	}
	
	public int peek() {
		if (top == null)
			return Integer.MIN_VALUE;

		int n = top.data;
		return n;
	}
	
	public boolean isEmpty() {
		if (top == null)
			return true;
		else
			return false;
	}
	
	public int getMin(){
		if(top == null)
			return Integer.MIN_VALUE;
		else
			return top.getMin();
	}
	

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		StackWithMin1 stack = new StackWithMin1();
		stack.push(8);
		stack.push(10);
		stack.push(13);
		stack.push(2);
		stack.push(6);
		System.out.println(stack.peek());
		System.out.println(stack.isEmpty());
		System.out.println(stack.getMin());
		System.out.println(stack.pop());
		System.out.println(stack.getMin());
		System.out.println(stack.pop());
		System.out.println(stack.getMin());
	}

}
